package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code89PartitionEqualSubsetSum {

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 只能是偶数
        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
        // 不可能存在比 target 大的数
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }
//        return process(nums, 0, target);

        boolean[][] dp = new boolean[nums.length][target + 1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int rest = 1; rest <= target; rest++) {
                dp[i][rest] = dp[i + 1][rest];
                if (rest >= nums[i]) {
                    dp[i][rest] |= dp[i + 1][rest - nums[i]];
                }
            }
        }
        return dp[0][target];
    }

    public boolean process(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return rest == 0;
        }
        if (rest == 0) {
            return true;
        }

        // 不取 index
        boolean p = process(nums, index + 1, rest);
        // 取 index
        if (rest >= nums[index]) {
            p |= process(nums, index + 1, rest - nums[index]);
        }
        return p;
    }
}
